#include <iostream>
#include <map>
using namespace std;

struct Node{
    int data;
    Node *left,*right;
};
Node* createTree(int h,map<int ,pair<int,int> > &tree){
		if( h!= -1){
		Node *ret = new Node();
		ret->data = h;
		ret->left = createTree(tree[h].first,tree);
		ret->right= createTree(tree[h].second,tree);
		return ret;
	}else return NULL;
}
void find(Node *head,int v,Node **get){
	if( head != NULL ){
		if( head->data == v){
			*get = head;
			
			return;
		}
		find(head->left,v,get);
		find(head->right,v,get);
	}
}
int findMostLeft(Node* h){
	while( h->left != NULL){
		h = h->left;
	}
	return h->data;
}
void findParent(Node *h,int v,Node **get){
	if( h ){
		if( h->left !=NULL && h->left->data== v)  *get = h;
		else if( h->right !=NULL && h->right->data == v ) *get = h;
		else {
			findParent(h->left,v,get);
			findParent(h->right,v,get);
		}
	}
}
void swap(Node *h,int b,int c ){
	Node *bP = NULL;
	Node *cP = NULL;
	Node *bPionter = NULL;
	Node *cPionter = NULL;
	findParent(h,b,&bP);
	findParent(h,c,&cP);
	find(h,b,&bPionter);
	find(h,c,&cPionter);
	if( cP!= bP){	
		if( bP->left!=NULL && bP->left->data == b ){
			bP->left = cPionter;
			if( cP->left!=NULL && cP->left->data== c){
				cP->left = bPionter;
			}else {
				cP->right = bPionter;
			}
		}else{
			bP->right = cPionter;
			if( cP->left!=NULL && cP->left->data== c){
				cP->left = bPionter;
			}else {
				cP->right = bPionter;
			}
		}
	}else{
		if( bP->left->data==b){
			bP->left = cPionter;
			bP->right = bPionter;
		}else{
			bP->left = bPionter;
			bP->right = cPionter;
		}
	}
}
int main(){
	freopen("in.txt","r",stdin);
    int t;
    cin >> t;
    for(int i=0; i<t; i++){
        int n,m;
        cin >> n >> m;
        Node *head = NULL;
        map<int,pair<int,int> > tree;
        for(int j=0; j < n; j++){
            int a,b,c;
            cin >> a >> b >> c;
            tree[a] = make_pair(b,c);
        }
        head = createTree(0,tree);
        for(int k=0; k<m; k++){
            int a,b;
            cin >> a >> b;
            if( a==2 ){
            	Node *tmp = NULL;
				find(head,b,&tmp);
				cout << findMostLeft(tmp) << endl;
            }else if( a==1){
                int c;
                cin >> c;
                swap(head,b,c);
            }
        }
    }
    return 0;
}
